package com.study.leetcode;

import java.util.*;

//https://leetcode.cn/problems/word-transformer-lcci/
public class WordConvert {
    List<String> path = new ArrayList<>();
    List<String> result = new ArrayList<>();

    public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> visited = new HashSet<>();
        DFS(beginWord, endWord, wordList, visited);
        return path;
    }

    private boolean DFS(String beginWord, String endWord, List<String> wordList, Set<String> visited) {
        path.add(beginWord);
        visited.add(beginWord);
        if (beginWord.equals(endWord)) {
            result.addAll(new ArrayList<>(path));
            return true;
        }
        for (String s : wordList) {
            if (!visited.contains(s) && check(beginWord, s)) {
                if (DFS(s, endWord, wordList, visited)) {
                    return true;
                }
            }
        }
        path.remove(beginWord);
        //visited不用回退，因为不论上一次搜索有没有成功下一次都需要剔除这个单词
        return false;
    }

    private boolean check(String beginWord, String s) {
        int flag = 0;
        for (int i = 0; i < beginWord.length(); i++) {
            if (s.charAt(i) != beginWord.charAt(i)) {
                flag++;
            }
        }
        return flag == 1;
    }

    public static void main(String[] args) {
        WordConvert wordConvert = new WordConvert();
        String beginWord = "hit";
        String endWord = "cog";
        List<String> wordList = Arrays.asList("hot", "dot", "dog", "cog", "lot", "log");
        List<String> ladders = wordConvert.findLadders(beginWord, endWord, wordList);
        System.out.println("ladders = " + ladders);
    }
}
